#include "BreadthFirstSearch.h"


BreadthFirstSearch::BreadthFirstSearch(void)
{
}


BreadthFirstSearch::~BreadthFirstSearch(void)
{
}

const char* BreadthFirstSearch::getFileName() {
	return "BreadthFirstSearch.gpi";
}

void BreadthFirstSearch::performSearch(node* start, node* goal, Grapher* gr, bool penalized, int maxExpandVectors) {
	queue.push(queue_node::newQN(0, start));

	node* current = NULL;
	node* next = NULL;
	edge* e = NULL;
	queue_node qn;
	goal->isGoal = true;
	int count = 1;
	int secondCount = 0;
	Vector2 vGoal(goal->x, goal->y);

	while(!queue.empty()) {
		qn = queue.front();
		queue.pop();

		current = qn.graph_node;

		if (current->isGoal) break;
		if (current->flag == 1) continue;

		current->flag = 1;

		if (gr != NULL && current->previous != NULL) {
			gr->addVector(Vector2(current->previous->x, current->previous->y), Vector2(current->x, current->y), 3);
		}

		for(int i = 0; i < current->neighbors.size(); i ++){
			e = &current->neighbors[i];
			next = e->to;
			
			if(next->flag == 1 || next->flag == 2) continue;

			next->previous = current;
			next->cost = qn.pathCost + e->weight;
			next->flag = 2;
			queue.push(queue_node::newQN(next->cost, qn.pathCost + e->weight, next));
		}

		secondCount ++;
		if(maxExpandVectors > 0 && secondCount >= maxExpandVectors) break;
		if(secondCount % 1000 == 0)
			std::cout  << "Expanded " << secondCount << " nodes\n";
	}
}
